import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
class Activity {
    int start;
    int finish;

    public Activity(int start, int finish) {//构造函数
        this.start = start;
        this.finish = finish;
    }
}

public class ActivitySelection {
    // 使用贪心算法选择最大数量的相容活动
    public static List<Activity> selectActivities(Activity[] activities) {
        List<Activity> selectedActivities = new ArrayList<>();


        // 根据活动的结束时间进行排序
        Arrays.sort(activities, new Comparator<Activity>() {
            public int compare(Activity a1, Activity a2) {
                return Integer.compare(a1.finish, a2.finish);
            }
        });


        // 将第一个活动加入选取列表
        selectedActivities.add(activities[0]);
        //设置第一个活动的结束时间为第一次的参考时间
        int previousFinishTime = activities[0].finish;
        // 从第二个活动开始遍历所有活动
        for (int i = 1; i < activities.length; i++) {
            Activity currentActivity = activities[i];
            // 如果当前活动的开始时间晚于前一个活动的结束时间，则选择该活动
            if (currentActivity.start >= previousFinishTime) {
                selectedActivities.add(currentActivity);
                previousFinishTime = currentActivity.finish;
            }else if (currentActivity.finish < previousFinishTime) {
                // 在后续的选择中再次比较并选择当前状态下的最优解
                selectedActivities.remove(selectedActivities.size() - 1);
                selectedActivities.add(currentActivity);
                previousFinishTime = currentActivity.finish;
            }
        }
        return selectedActivities;
    }

    public static void main(String[] args) {
        Activity[] activities = {new Activity(1, 4),
                new Activity(3, 5),
                new Activity(0, 6),
                new Activity(5, 7),
                new Activity(3, 9),
                new Activity(5, 9),
                new Activity(6, 10),
                new Activity(8, 11),
                new Activity(8, 12),
                new Activity(2, 14),
                new Activity(12, 16)};
        //使用贪婪算法选择最大数量的相容活动,调用selectActivities方法，用selectedActivities接收
        List<Activity> selectedActivities = selectActivities(activities);
        //输出选取的相容活动
        System.out.println("Selected Activities:");
        //打印被安排的活动顺序
        for (Activity activity : selectedActivities) {
            System.out.println("[" + activity.start + ", " + activity.finish + "]");
        }
    }
}
